#include <iostream>
#include <vector>

using namespace std;

class Solution {
private:
    int64_t help_n(vector<int>& arr, int k) {
        int64_t old = 0;
        int64_t max_sum = 0;
        for (int k = 2; k > 0; k--) {
            for (int num: arr) {
                old > 0 ? old = num + old : old = num;
                max_sum = max(max_sum, old);
            }
        }
        return max_sum;
    }
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int64_t max_sum;
        switch (k) {
            case 0:
                return 0;
            case 1:
                max_sum = help_n(arr, 1);
                break;
            case 2:
                max_sum = help_n(arr, 2);
                break;
            default:
                max_sum = help_n(arr, 2);
                int64_t arr_sum = 0;
                for (int num: arr) {
                    arr_sum += num;
                }
                if (arr_sum > 0) {
                    max_sum += int64_t(k - 2) * arr_sum;
                }
                break;
        }
        if (max_sum >= 1e9 + 7) {
            return max_sum % int64_t(1e9 + 7);
        }
        return max_sum;
    }
};


int main() {
    Solution solution;
    vector<int> arr = {-5,-2,0,0,3,9,-2,-5,4};
    int k = 5;
    int out = solution.kConcatenationMaxSum(arr, k);
    cout << out << endl;
}